Date: Wed, 08 Jan 1997 20:46:43 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322  
Assignment 1 Solution Set  
Friday, January 12, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322  
Assignment 1 Solution Set  
Friday, January 12, 1996">
<meta name="keywords" value="hw1soln">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322  
Assignment 1 Solution Set  
Friday, January 12, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI> 
Prove that <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif"> for all <b>n &gt; 0</b>. (#27 p. 27)
<P>
We can prove this by induction on <b>n</b>:
<P>
<b>Basis:</b> The statement is true for <b>n = 1</b> because
<IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif">.
<P>
<b>Inductive hypothesis:</b> Assume that the statement is true for <b>n=k</b>:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img3.gif"><P>
<b>Inductive step:</b> From this we need to show it is true for <b>n=k+1</b>:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img4.gif"><P>
By induction, the statement is true for all <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">.
<P>
<LI> Using the tree on p. 27:(#27 p. 27)
<OL><LI> The depth of the tree is 4.  (The depth of the root is 0.)
<LI> The ancestors of <IMG  ALIGN=MIDDLE ALT="" SRC="img6.gif"> are <IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif">,<IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">,<IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif">, and <IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">.
(Every node is an ancestor of itself.)
<LI> The minimal common ancestor of <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif"> is <IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif"> and
of <IMG  ALIGN=MIDDLE ALT="" SRC="img14.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img15.gif"> is <IMG  ALIGN=MIDDLE ALT="" SRC="img16.gif">.
<LI> The subtree generated by <IMG  ALIGN=MIDDLE ALT="" SRC="img17.gif"> is the following:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img18.gif"><P>
<LI> The frontier of the tree is <IMG  ALIGN=MIDDLE ALT="" SRC="img19.gif">.
</OL>
<LI> 
<OL><LI>
The rank of <IMG  ALIGN=BOTTOM ALT="" SRC="img20.gif"> in the enumeration ordering of <IMG  ALIGN=MIDDLE ALT="" SRC="img21.gif"> is 
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img22.gif"><P>
This is because if we look at the strings of length <b>2n</b>, the first strings
in the enumeration are those that begin with <IMG  ALIGN=BOTTOM ALT="" SRC="img23.gif">.  
Of the strings that begin with <IMG  ALIGN=BOTTOM ALT="" SRC="img24.gif">, <IMG  ALIGN=BOTTOM ALT="" SRC="img25.gif"> is the first
and <IMG  ALIGN=BOTTOM ALT="" SRC="img26.gif"> is the last of these.  This gives us the following:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img27.gif"><P>
The rank of <IMG  ALIGN=BOTTOM ALT="" SRC="img28.gif"> is <IMG  ALIGN=BOTTOM ALT="" SRC="img29.gif">.
The number of strings  of length <b>2n</b> that begin with <IMG  ALIGN=BOTTOM ALT="" SRC="img30.gif"> is just
the number of ways of writing the last <b>n</b> letters as a string in the alphabet.
There are <IMG  ALIGN=BOTTOM ALT="" SRC="img31.gif"> such ending strings.  Combining these observations gives us:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img32.gif"><P>
<P>
<LI>
The rank of <IMG  ALIGN=BOTTOM ALT="" SRC="img33.gif"> in the enumeration ordering of <IMG  ALIGN=MIDDLE ALT="" SRC="img34.gif"> is
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img35.gif"><P>
In the enumeration ordering, the strings that come before <IMG  ALIGN=BOTTOM ALT="" SRC="img36.gif"> are exactly
the strings over <IMG  ALIGN=MIDDLE ALT="" SRC="img37.gif"> whose length is less than <b>n</b>.  Therefore,
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img38.gif"><P>
For any <b>i</b>, the number of strings of length <b>i</b> is <IMG  ALIGN=BOTTOM ALT="" SRC="img39.gif">.  
Thus the number of strings of length less than <b>n</b> is the sum of all these,
so:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img40.gif"><P></OL></OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Mon Jan 29 18:05:51 PST 1996</I>
</ADDRESS>
</BODY>
